package com.LC._860;
//因为需要使用 55 美元的找零场景会比需要使用 1010 美元的找零场景多，我们需要尽可能保留 55 美元的钞票。
//public class Solution {
//    public boolean lemonadeChange(int[] bills) {
//        int five = 0;//记录钞票的个数
//        int ten = 0;//记录钞票的个数
//        int twenty = 0;//记录钞票的个数
//        int change;//别人的给的零钱
//        for (int i = 0; i < bills.length; i++) {
//            // 需要找零的金额
//            change = bills[i] - 5;
//            // 能找20就20
//            while (change >= 20 && twenty > 0) {
//                change -= 20;
//                twenty--;
//            }
//
//            // 其次找10块
//            while (change >= 10 && ten > 0) {
//                change -= 10;
//                ten--;
//            }
//
//            // 然后找5块
//            while (change >= 5 && five > 0) {
//                change -= 5;
//                five--;
//            }
//
//            // 无法找零
//            if (change > 0) return false;
//
//            if (bills[i] == 20) twenty++;
//            else if (bills[i] == 10) ten++;
//            else five++;
//        }
//
//        return true;
//    }
//}
//class Solution {
//    public boolean lemonadeChange(int[] bills) {
//        int five =0;
//        int ten =0;
//        for(int bill :bills){
//            if(bill==5){
//                five++;
//            }else if(bill==10){
//                if(five==0){
//                    return false;
//                }
//                ten++;
//                five--;
//            }else if(bill==20){
//                if(ten>0&&five>0){
//                    ten--;
//                    five--;
//                }else if(five>=3){
//                    five-=3;
//                }else{
//                    return false;
//                }
//            }
//        }
//        return true;
//
//    }
//}

public class Solution {

    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }

        // 0：持有现金
        // 1：持有股票
        // 状态转移：0 → 1 → 0 → 1 → 0 → 1 → 0
        int[][] dp = new int[len][2];

        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i < len; i++) {
            // 这两行调换顺序也是可以的
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[len - 1][0];
    }
}